package LeetCode;

import java.util.*;

public class LC_103_BinaryTreeZigzagLevelOrderTraversal {
    public static void main(String[] args) {

    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution_1 {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) return result;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            int i = queue.size();
            boolean flag = false;
            TreeNode tempNode;
            List<Integer> singleLevel = new ArrayList<>();
            while (!queue.isEmpty()) {
                if (i == 0) {
                    if (flag) Collections.reverse(singleLevel);
                    result.add(singleLevel);
                    flag = !flag;
                    i = queue.size();
                    singleLevel = new ArrayList<>();
                }
                tempNode = queue.poll();
                singleLevel.add(tempNode.val);
                --i;
                if (tempNode.left != null) queue.add(tempNode.left);
                if (tempNode.right != null) queue.add(tempNode.right);
            }
            if (flag) Collections.reverse(singleLevel);
            result.add(singleLevel);
            return result;
        }

    }

    static class Solution_2 {
        public List<List<Integer>> zigzagLevelOrder5(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) return result;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            int i = queue.size();
            boolean flag = true;
            TreeNode tempNode;
            LinkedList<Integer> singleLevel = new LinkedList<>();
            while (!queue.isEmpty()) {
                if (i == 0) {
                    result.add(singleLevel);
                    i = queue.size();
                    singleLevel = new LinkedList<>();
                    flag = !flag;
                }
                tempNode = queue.poll();
                if (flag) {
                    singleLevel.add(tempNode.val);
                } else {
                    singleLevel.addFirst(tempNode.val);
                }
                --i;
                if (tempNode.left != null) queue.offer(tempNode.left);
                if (tempNode.right != null) queue.offer(tempNode.right);
            }
            result.add(singleLevel);
            return result;
        }

    }

    static class Solution_3 {
        public List<List<Integer>> zigzagLevelOrder2(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            // levelRecursion(root, result, 0, false);
            levelRecursion2(root, result, 0);
            return result;
        }

        private void levelRecursion(TreeNode node, List<List<Integer>> result, int level, boolean flag) {
            if (node == null)
                return;
            if (result.size() < level + 1)
                result.add(new LinkedList<>());
            if (flag)
                ((LinkedList<Integer>) result.get(level)).addFirst(node.val);
            else
                result.get(level).add(node.val);
            levelRecursion(node.left, result, level + 1, !flag);
            levelRecursion(node.right, result, level + 1, !flag);
        }

        private void levelRecursion2(TreeNode node, List<List<Integer>> result, int level) {
            if (node == null)
                return;
            if (result.size() < level + 1)
                result.add(new LinkedList<>());
            if (level % 2 != 0)
                ((LinkedList<Integer>) result.get(level)).addFirst(node.val);
            else
                result.get(level).add(node.val);
            levelRecursion2(node.left, result, level + 1);
            levelRecursion2(node.right, result, level + 1);
        }

    }

    static class Solution_4 {
        public List<List<Integer>> zigzagLevelOrder3(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) return result;
            Stack<TreeNode> forwardStack = new Stack<>();
            Stack<TreeNode> retrorseStack = new Stack<>();
            forwardStack.push(root);
            TreeNode tempNode;
            List<Integer> singleList = new ArrayList<>();
            while (!forwardStack.isEmpty() || !retrorseStack.isEmpty()) {
                while (!forwardStack.isEmpty()) {
                    tempNode = forwardStack.pop();
                    singleList.add(tempNode.val);
                    if (tempNode.left != null) retrorseStack.push(tempNode.left);
                    if (tempNode.right != null) retrorseStack.push(tempNode.right);
                }
                if (!singleList.isEmpty()) {
                    result.add(singleList);
                    singleList = new ArrayList<>();
                }
                while (!retrorseStack.isEmpty()) {
                    tempNode = retrorseStack.pop();
                    singleList.add(tempNode.val);
                    if (tempNode.right != null) forwardStack.push(tempNode.right);
                    if (tempNode.left != null) forwardStack.push(tempNode.left);
                }
                if (!singleList.isEmpty()) {
                    result.add(singleList);
                    singleList = new ArrayList<>();
                }
            }
            return result;
        }
    }

    static class Solution_5 {
        public List<List<Integer>> zigzagLevelOrder4(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) return result;
            boolean flag = true;
            TreeNode tempNode;
            TreeNode lastNode = root;
            List<Integer> singleLevel = new ArrayList<>();
            Deque<TreeNode> deque = new LinkedList<>();
            deque.offer(root);
            while (!deque.isEmpty()) {
                tempNode = flag ? deque.pollFirst() : deque.pollLast();
                singleLevel.add(tempNode.val);
                if (flag) {
                    if (tempNode.left != null) deque.offerLast(tempNode.left);
                    if (tempNode.right != null) deque.offerLast(tempNode.right);
                } else {
                    if (tempNode.right != null) deque.offerFirst(tempNode.right);
                    if (tempNode.left != null) deque.offerFirst(tempNode.left);
                }
                if (tempNode == lastNode) {
                    result.add(singleLevel);
                    singleLevel = new ArrayList<>();
                    lastNode = flag ? deque.peekFirst() : deque.peekLast();
                    flag = !flag;
                }
            }
            return result;
        }
    }
}
